package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-31
 */

import java.util.Arrays;

/**
 * 这里有n个航班，它们分别从 1 到 n 进行编号。
 *
 * 有一份航班预订表bookings ，
 * 表中第i条预订记录bookings[i] = [firsti, lasti, seatsi]意味着在从 firsti到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi个座位。
 *
 * 请你返回一个长度为 n 的数组answer，其中 answer[i] 是航班 i 上预订的座位总数。
 */
public class leetcode1109 {
    //暴力解法
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        for (int i = 0; i < bookings.length; i++) {
            for (int j = bookings[i][0]; j <= bookings[i][1]; j++) {
                res[j] += bookings[i][2];
            }
        }
        return res;
    }
    //差分解法
    //获得一段区间，反向求前缀和，起点加上bookings[2]，终点+1减去bookings[2]（可以理解为上下车，求每个位置车上有多少人）
    public int[] corpFlightBookings2(int[][] bookings, int n) {
        int[] counts = new int[n];
        for (int[] booking : bookings) {
            counts[booking[0]-1] += booking[2];
            if (booking[1]<n) counts[booking[1]] -= booking[2];
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i-1];
        }
        return counts;
    }
}
